from functools import cache
from typing import List

# 递归的递是把当前状态看作起始状态，当前操作是考虑怎么递归到下一个状态
# 递归的归是把当前操作看作最终状态，当前操作是怎么由前一个过程来的，递归回去
# dp是把当前状态看作最终状态，它的状态由前一个i-1,j-1相关得来
# 递归的归 == dp操作
# 把递归的递改写dp，i,j不变， + - 操作 变为 - + 操作，其他看意思改写

# 选择一方法 粘贴运行

# 方法一：dfs+记忆化搜索
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        # dfs+记忆化搜索cache
        @cache
        # 对于当前元素 i 满足条件 就选，取最长的长度
        def dfs(i):
            if i == len(nums) - 1:
                return 1
            max_len = 1
            for j in range(i + 1, len(nums)):
                # 满足条件，递增 选
                if nums[i] < nums[j]:
                    max_len = max(max_len, dfs(j) + 1)
                # 不满足条件，不做处理，遍历的时候 条件判断 已经跳过
            return max_len

        return max(dfs(i) for i in range(len(nums)))

# 方法二：dp
# 定义dp[i]，表示
# 转移方程：如果nums[j] > nums[i]，dp[i] = dp[j] + 1。
# 初始状态：dp[i] = 1，表示只有一个元素的递增子序列。
# 时间复杂度：O(n^2)，空间复杂度：O(n)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        dp = [1] * len(nums)
        # dp[i] 以i结尾的最长上升子序列
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i + 1, len(nums)):
                # 后一个大于 前一个 严格上升
                if nums[j] > nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

# 方法三：
"""贪心+二分。
维护一个单调递增的数组d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值。起始长度为1，d[1] = nums[0].
以输入序列 [0, 8, 4, 12, 2] 为例：
第一步插入 0，d=[0]；
第二步插入 8，d=[0,8]；
第三步插入 4，d=[0,4]；
第四步插入 12，d=[0,4,12]；
第五步插入 2，d=[0,2,12]。
最终得到最大递增子序列长度为 3。
时间复杂度：O(nlogn)，空间复杂度：O(n)
"""
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 方法三:
        # 维护单调递增数组
        n = len(nums)
        d = [0] * (n + 1)
        length = 1
        d[length] = nums[0]

        for i in range(1, n):
            # 要加入的数 > 当前数组的最大值 加入末尾
            if nums[i] > d[length]:
                length += 1
                d[length] = nums[i]
            else:
                # left 小于目标值的情况
                # right 大于 等于 目标值
                # 左闭 右开区间 [left,right)
                left, right = 0, length + 1
                while left+1< right:
                    mid = left + (right - left) // 2
                    if d[mid] < nums[i]:
                        left = mid
                    else:
                        right = mid
                d[right] = nums[i]
        return length

